package leecode.array.子串与子序列问题;

import java.util.HashSet;
import java.util.Set;

/**
 * @author wangxi created on 2021/5/29 21:17
 * @version v1.0
 *
 * 最长数字连续子序列
 *
 * 给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。
 *
 *  https://leetcode-cn.com/problems/longest-consecutive-sequence/
 *
 * 进阶：你可以设计并实现时间复杂度为 O(n) 的解决方案吗？

 *
 */
public class LongestConsecutiveSequence {

    public int longestConsecutive(int[] nums) {
        if (nums == null || nums.length <= 0) {
            return 0;
        }
        Set<Integer> set = new HashSet<>();
        // 利用set记录O(1)访问
        for (int num : nums) {
            set.add(num);
        }
        int res = 0;
        // 遍历set 以去重相对于nums
        for (int num : set) {
            if (!set.contains(num - 1)) {
                int cur = 1;
                while (set.contains(num + 1)) {
                    cur++;
                    num++;
                }
                res = Math.max(res, cur);
            }
        }
        return res;
    }

    public int longestConsecutive1(int[] nums) {
        if (nums == null || nums.length <= 0) {
            return 0;
        }
        Set<Integer> set = new HashSet<>();
        // 利用set记录O(1)访问
        for (int num : nums) {
            set.add(num);
        }
        int res = 0;
        // 注意：遍历nums 这种写法 提交会超时。。 看评论的解释是set会去重
        // 看了下超时的测试用例，确实很多重复的元素
        for (int num : nums) {
            if (set.contains(num + 1)) {
                continue;
            }
            int cur = 1;
            while (set.contains(num - 1)) {
                cur++;
                num--;
            }
            res = Math.max(res, cur);
        }
        return res;
    }
}
